package com.leetcode.sorts.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: WuPeng
 * @Date: 2021/6/8 2:36 下午
 *
 * 113.路径总和2
 *
 */
public class PathSum_113 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root,targetSum);
        return res;
    }

    private void dfs(TreeNode node, int sum) {
        if (node == null) return;
        sum -= node.val;
        path.add(node.val);
        if (node.left == null && node.right == null && sum == 0){
            res.add(new ArrayList<>(path));
        }
        dfs(node.left, sum);
        dfs(node.right, sum);
        path.remove(path.size()-1);
    }

}
